GATE CSE 2018
Q31.
Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is X units. Which one of the following is the correct expression for the page fault rate experienced by the process?Q32.
Consider the following undirected graph G: Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ______.Q33.
Given a language L, define L^{i} as follows: L^{0}=\{\varepsilon \} L^{i}=L^{i-1} \cdot L for all i \gt 0 The order of a language L is defined as the smallest k such that L^{k}=L^{k+1}. Consider the language L1 (over alphabet 0) accepted by the following automaton. The order of L1 is ______Q34.
Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?Q35.
Consider the unsigned 8-bit fixed point binary Number System below, b_7 b_6 b_5 b_4 b_3 . b_2 b_1 b_0 where the position of the binary point is between b_3 \; and \; b_2. Assume b_7 is the most significant bit. Some of the decimal numbers listed below cannot be represented exactly in the above representation: (i) 31.500 (ii) 0.875 (iii) 12.100 (iv) 3.001 Which one of the following statements is true?Q36.
Consider the following four relational schemas. For each schema, all non-trivial functional dependencies are listed. The underlined attributes are the respective primary keys. Which one of the relational schemas above is in 3NF but not in BCNF?Q37.
A processor has 16 integer registers (R0, R1,...,R15) and 64 floating point registers (F0, F1,...,F63). It uses a 2-byte instruction format. There are four categories of instructions: Type-1, Type-2, Type-3, and Type-4. Type-1 category consists of four instructions, each with 3 integer register operands (3Rs). Type-2 category consists of eight instructions, each with 2 floating point register operands (2Fs). Type-3 category consists of fourteen instructions, each with one integer register operand and one floating point register operand (1R+1F). Type-4 category consists of N instructions, each with a floating point register operand (1F). The maximum value of N is __________.Q38.
C onsider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #. Which one of the following is correct for the given parse tree?Q39.
Consider the following processor design characteristics. I. Register-to-register arithmetic operations only II. Fixed-length instruction format III. Hardwired control unit Which of the characteristics above are used in the design of a RISC processor?Q40.
The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. Assume that there are no data hazards and no control hazards. The number of clock cycles required for completion of execution of the sequence of instructions is ______.